package com.fengdi.publicObject;

/**
 * @Description 线段树
 * @Date 21:45
 */


public class SegmentTree<T> {
    private final T[] tree;
    private final T[] data;
    private Merger<T> merger;

    public SegmentTree(T[] arr, Merger<T> merger) {
        this.merger = merger;
        this.data = (T[]) new Object[arr.length];

        System.arraycopy(arr, 0, this.data, 0, arr.length);

        tree = (T[]) new Object[4 * arr.length];
        this.buildSegmentTree(0, 0, arr.length - 1);
    }

    private void buildSegmentTree(int treeIndex, int l, int r) {
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }

        int leftChildIndex = this.leftChildIndex(treeIndex);
        int rightChildIndex = this.rightChildIndex(treeIndex);

        int mid = l + (r - l) / 2;
        this.buildSegmentTree(leftChildIndex, l, mid);
        this.buildSegmentTree(rightChildIndex, mid + 1, r);

        tree[treeIndex] = merger.merger(tree[leftChildIndex], tree[rightChildIndex]);
    }

    public int getSize() {
        return this.data.length;
    }

    public T get(int index) {
        if(index < 0 || index >= this.data.length) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        return this.data[index];
    }

    private int leftChildIndex(int fatherIndex) {
        return 2 * fatherIndex + 1;
    }

    private int rightChildIndex(int fatherIndex) {
        return 2 * fatherIndex + 2;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append('[');
        for(int i = 0 ; i < tree.length ; i++){
            if(tree[i] != null)
                res.append(tree[i]);
            else
                res.append("null");

            if(i != tree.length - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }

}
